分散 algorithm
同時編緝
v.s.
合意
傳播
gossip protocol
transaction
調整者 (coordinator)
參加者 (cohorts)
code:mmd
sequenceDiagram
participant 調整者
participant 參加者
調整者 ->> 參加者 : commit要求
調整者 ->> 調整者 : commit要求狀態に移行
參加者 ->> 參加者 : commit準備
參加者 -->> 調整者 : OK
調整者 ->> 參加者 : commit
調整者 ->> 調整者 : commit狀態に移行
參加者 ->> 參加者 : commit
code:mmd
sequenceDiagram
participant 調整者
participant 參加者1
participant 參加者2
調整者 ->> 參加者1 : commit要求
調整者 ->> 參加者2 : commit要求
參加者1 ->> 參加者1 : commit準備
參加者1 -->> 調整者 : OK
參加者2 -->> 調整者 : NG
調整者 ->> 參加者1 : rollback
調整者 ->> 參加者2 : rollback
參加者1 ->> 參加者1 : rollback
code:mmd
分散データベースシステムにおける原子的コミットプロトコルのための形式的モデルが提案される。このモデルは、ネットワークを分割しないサイト障礙に對する耐障礙性プロトコルの存在性を證明するために用ゐられる。さらに、ネットワークが分割された場合についても考察する。サイト障礙に關しては、「獨立恢復」と呼ばれる悲觀的恢復手法を導入し、耐障礙性プロトコルが存在し得る障礙のクラスを特定する。ネットワークが分割された場合については、2 つのケースを詳細に檢討する : メッセージが消失する悲觀的ケースと、メッセージが消失しない樂觀的ケースである。いづれの場合においても、プロトコルの耐障礙性に關する根本的な制約條件が導出される。
timeout を取り扱へる
code:mmd
sequenceDiagram
participant 調整者
participant 參加者
調整者 ->> 參加者 : canCommit?
調整者 ->> 調整者 : 待機狀態に移行
參加者 -->> 調整者 : Yes
調整者 ->> 參加者 : preCommit
調整者 ->> 調整者 : 準備狀態に移行
參加者 ->> 參加者 : commit
參加者 -->> 調整者 : ACK
調整者 ->> 調整者 : commit狀態に移行
messaging
AMQP (advanced message queuing protocol)
WebSub
a.k.a. PubSubHubbub
Chord
Kademlia
proof of X
lightning network
應用
純粹なP2P (peer to peer)型電子通貨システムを導入すれば、オンライン決濟は金融機關を介さずに直接的に當事者閒で行へるやうになる。digital 署名はこの問題の解決に寄與する要素ではあるが、二重使用を防止するための信賴できる第三者機關が依然として必要とされる場合、システムの主要な利點が失はれてしまふ。 本論文では、P2P (peer to peer)ネットワークを利用した二重使用問題の解決策を提案する。本ネットワークでは、取引をハッシュ化して繼續的なハッシュベースのプルーフ・オブ・ワーク連鎖に記錄することで、取引時點を證明する。これにより、プルーフ・オブ・ワークを再實行することなく記錄內容を改竄することは不可能となる。最も長い連鎖は、單に一聯の取引順序を證明するだけでなく、それが最も多くの CPU リソースプールから生成されたことの證左ともなる。ネットワークの過半數の CPU リソースが攻擊目的で協調してゐないノードによって制禦されてゐる限り、これらのノードは最も長い連鎖を生成し續け、攻擊者を上囘る速度で更新を行ふ。本ネットワーク自體に必要な構造は最小限である。メッセージは最善を盡くしてブロードキャストされ、ノードは任意のタイミングでネットワークへの參加・離脱が可能であり、不在期閒中に起こった取引の證明として、最長のプルーフ・オブ・ワーク連鎖を受け入れる仕組みとなってゐる。 Ethereum
NFT (non-fungible token)
DNS にも應用がある
fediverse
Facebook Threads
OStatus
Freenet
Tor